public class MySingelList {
    ListNode headNode = null;

    //1.无循环单向链表
    public void addFirst(int data) {
        if (this.headNode == null) {
            this.headNode = new ListNode(data);
        } else {
            ListNode newNode = new ListNode(data);
            newNode.nextNode = headNode;
            headNode = newNode;//!!!
        }
    }

    //尾插法
    public void addLast(int data) {
        if (this.headNode == null) {
            this.headNode = new ListNode(data);
        } else {
            ListNode newNode = new ListNode(data);
            //通过循环找到最后一个节点
            ListNode node = this.headNode;
            while (node.nextNode != null) {
                node = node.nextNode;
            }
            node.nextNode = newNode;
        }
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        //头插
        if (index == 0) {
            this.addFirst(data);
            return;
        }

        ListNode node = this.headNode.nextNode;
        ListNode curNode = this.headNode;

        int i = 0;
        while (i < index - 1) {
            curNode = curNode.nextNode;
            node = node.nextNode;
            i++;
        }

        ListNode newNode = new ListNode(data);
        curNode.nextNode = newNode;
        newNode.nextNode = node;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode node = this.headNode;
        while (node.nextNode != null) {
            if (node.value == key) {
                return true;
            }
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //三个指针一起迭代，当 node 指针确认删除目标后，curNode.nextNode = nextnode
        ListNode node = headNode;
        ListNode nextnode = node.nextNode;

        ListNode curnode = null;


        /*
          当 node 指向最后一个节点时，nextnode 为空！！！
         */
        while (node.nextNode != null) { //node最多指向最后一个节点
            if (headNode.value == key) {
                //头删
                this.headNode = headNode.nextNode;
                return;
            } else if (node.value == key) {
                curnode.nextNode = nextnode;
                node.nextNode = null;
                return;
            }
            curnode = node;
            node = node.nextNode;
            if (nextnode.nextNode != null) {
                nextnode = nextnode.nextNode;
            }
            //循环条件的更新
        }
        //循环结束，只有尾删一种情况(node.nextNode == null)
        if (curnode != null) {
            curnode.nextNode = null;
        }

    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        // 让 node 直接跳到要删除的部分

        if (headNode == null) {
            System.out.println("链表为空，删个蛋");
            return;
        }

        //将headnode 指向到不是关键字为止
        //整个链表全是关键字
        while (headNode.value == key) {
            headNode = headNode.nextNode;
            if (headNode.nextNode == null) {
                headNode = null;
                return;
            }
        }
        //链表都是关键字怎么办？？？ -> 一删到底了！！！ headnode 直接为空啦，加个检查
        ListNode node = headNode;   //不要轻易动 头节点
        ListNode nextnode = node.nextNode;

        while (node.nextNode != null) {
            if (nextnode.value == key) {
                node.nextNode = nextnode.nextNode;
                nextnode.nextNode = null;
            } else {
                //迭代条件
                node = node.nextNode;
                nextnode = nextnode.nextNode;
            }
        }
    }

    //得到单链表的长度
    public int size() {
        int num = 0;
        ListNode node = this.headNode;
        while (node != null) {
            num++;
            node = node.nextNode;
        }
        return num;
    }

//    public void clear() {
//       this.headNode = null;
//    }

    public void clear() {
        ListNode x = this.headNode;
        ListNode nextnode = x.nextNode;

        while (x.nextNode != null) {
            x.nextNode = null;
            x = nextnode;
            if (nextnode.nextNode != null) {
                nextnode = nextnode.nextNode;
            }
        }
        headNode.nextNode = null;
        headNode = null;

    }

    public void display() {
        ListNode node = this.headNode;
        while (node != null) {
            System.out.println(node.value);
            node = node.nextNode;
        }
    }

    //单独创建一个内部类，专门用来存放节点
    static public class ListNode {
        int value;
        ListNode nextNode = null; //大写N代表当前节点的下一个节点

        public ListNode(int value) {
            this.value = value;
        }
    }
}
